/*
有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.

以上就是著名的RPG难题.

如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?

 

Input
输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成，(0<n<=50)。

-----------------------------------------------
解题思路    这应该是一道找规律类推的题目   
先从特殊情况着手：   设格子数为n    当n=1时，必然只有三种情况红，绿，粉；    
当n=2时，第一个格子可以有三种情况，当第一个格子选定了一个颜色后，
第二个格子只能在剩下的两个中选一个，则有3*2=6种情况；    
当n=3时，第一个格子可以有三种情况，当第一个格子选定后，第二个格子有两种选择，
因为第二个格子和第一个格子颜色必然不同，所以第三个格子只能有一个选择，所以公有3*2*1=6种选择；   
当n=4时，第一个格子三种情况，第二个格子两种情况，当第三个格子和第一个格子不同时，
第四个格子可以有一种选择，当第三个格子和第一个格子相同时，第四个格子可以有两种情况，
这样共有3*2*1*1+3*2*1*2=18种(到这里可以看出递推公式好像是a(n)=a(n-1)+a(n-2)*2) 
由此类推到有n个格子，假设前n-1个格子有f(n-1)种情况，当第n-1个格子和第一个格子不同时，
则    第n个格子只有一种选择，所以一共有f(n-1)*1种情况；当第n-2个格子和第一个不同，
第n-1个格子和第一个格子相同时，那么第 n 个格子可以有两种选择，这样一来，共有f(n-2)*2种情况；
把这两种情况加起来一共有f(n-1)*1+f(n-2)*2
 */
package com.yuan.algorithms.acm201503;

import java.util.Scanner;

public class HD2045排列不同颜色的格子 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long[] arr = new long[51];
		arr[1] = 3;
		arr[2] = arr[3] = 6;
		for (int i = 4; i < arr.length; i++) {
			arr[i] = arr[i-1]+arr[i-2]*2;
		}
		while (sc.hasNext()) {
			int n = sc.nextInt();
			System.out.println(arr[n]);
		}
	}

}
